Single number

Time: O(N); Space: O(1); easy

Given an array of integers, every element appears twice except for one. Find that single one.

Example 1:

Input: A = [1, 1, 2, 2, 3]

Output: 3

Notes:

• Your algorithm should have a linear runtime complexity.

• Could you implement it without using extra memory?

import operator
from functools import reduce

class Solution1(object):

    def singleNumber(self, A) -> int:
        """
        :type A: List[int]
        :rtype: int
        """
        return reduce(operator.xor, A)

s = Solution1()
A = [1, 1, 2, 2, 3]
assert s.singleNumber(A) == 3

See also:

https://leetcode.com/problems/single-number

https://www.lintcode.com/problem/single-number